package srcTA;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

import lib.ArgumentValidator;
import lib.logging.ILogger;
import acm.util.RandomGenerator;

public class StateManager
{
    final private List<Bid> initialSetOfBids;
    private RandomGenerator randomGenerator;

    public StateManager(List<Bid> bids)
    {
        ArgumentValidator.IsNotNull("bids", bids);

        this.initialSetOfBids = bids;
        this.randomGenerator = RandomGenerator.getInstance();
    }

    private List<AcceptedBids> GenerateNeighborsByAddingBids(List<Bid> bids) 
    {
        List<Bid> availBids = new ArrayList<Bid>(initialSetOfBids);
        availBids.removeAll(bids);
        
        Collections.sort(availBids);
        
        // remove companies whose bids have already been accepted
        // use the fact that the bids are sorted by companyIDs
        for (int i = 0; i < bids.size(); ++i)
        {
            Bid bid = bids.get(i);
            List<Bid> bidsToRemove = new ArrayList<Bid>();

            int position = Collections.binarySearch(availBids, bid, new CompanyIdBasedBidComparer());
            
            if (position < 0)
            {
                continue;
            }
            
            for (int j = position; j >= 0; --j)
            {
                if (bid.Company() != availBids.get(j).Company())
                {
                    break;
                }
                
                bidsToRemove.add(availBids.get(j));
            }
            
            for (int j = position + 1; j < availBids.size(); ++j)
            {
                if (bid.Company() != availBids.get(j).Company())
                {
                    break;
                }
                
                bidsToRemove.add(availBids.get(j));
            }
            
            availBids.removeAll(bidsToRemove);
        }
        
        // remove regions whose bids have already been accepted
        for (Bid bid : bids)
        {
            List<Bid> bidsToRemove = new ArrayList<Bid>();
            
            for (Bid availBid : availBids)
            {
                List<Integer> availBidRegions = new ArrayList<Integer>(availBid.Regions());
                availBidRegions.retainAll(bid.Regions());
                if (availBidRegions.size() > 0)
                {
                    bidsToRemove.add(availBid);
                }
            }
            
            availBids.removeAll(bidsToRemove);
        }

        
        List<AcceptedBids> neighborStates = new ArrayList<AcceptedBids>();
        
        for (int i = 0; i < availBids.size(); ++i)
        {
            double currentTotalValue = 0;
            List<Bid> currentBids = new ArrayList<Bid>(bids);
            List<Integer> currentCompaniesCovered = new ArrayList<Integer>();
            List<Integer> currentRegionsCovered = new ArrayList<Integer>();
            
            currentTotalValue = PopulateDetailsFromBids(
                    bids,
                    currentCompaniesCovered,
                    currentRegionsCovered);

            boolean bidAdded = false;
            
            for (int j = i; j < availBids.size(); ++j)
            {
                Bid bid = availBids.get(i);
                
                if (currentCompaniesCovered.contains(bid.Company()))
                {
                    continue;
                }

                boolean isBidRegionCovered = false;
                for (int region : bid.Regions())
                {
                    if (currentRegionsCovered.contains(region))
                    {
                        isBidRegionCovered = true;
                        break;
                    }
                }
                
                if (!isBidRegionCovered)
                {
                    bidAdded = true;
                    currentTotalValue += bid.Value();
                    currentBids.add(bid);
                    currentCompaniesCovered.add(bid.Company());
                    currentRegionsCovered.addAll(bid.Regions());
                }
            }
            
            if (bidAdded)
            {
                neighborStates.add(
                        new AcceptedBids(
                                currentBids,
                                currentTotalValue,
                                currentCompaniesCovered,
                                currentRegionsCovered));
            }
        }
        
        return neighborStates;
    }

    public AcceptedBids GetGreedyPerRegionCostInitialState() 
    {
        List<Bid> allBids = new ArrayList<Bid>(initialSetOfBids);
        Collections.sort(allBids, new CostPerRegionBasedBidComparer());
        
        List<Bid> selectedBids = new ArrayList<Bid>();
        double totalValue = 0;
        List<Integer> currentCompaniesCovered = new ArrayList<Integer>();
        List<Integer> currentRegionsCovered = new ArrayList<Integer>();
        
        // try to fill in the bids just greedily now
        for (int i = 0; i < allBids.size(); ++i)
        {
            Bid bid = allBids.get(i);
            
            if (currentCompaniesCovered.contains(bid.Company()))
            {
                continue;
            }
            
            boolean isAnyRegionCovered = false;
            
            for (int region : bid.Regions())
            {
                if (currentRegionsCovered.contains(region))
                {
                    isAnyRegionCovered = true;
                    break;
                }
            }
            
            if (isAnyRegionCovered)
            {
                continue;
            }
            
            selectedBids.add(bid);
            currentCompaniesCovered.add(bid.Company());
            currentRegionsCovered.addAll(bid.Regions());
            totalValue += bid.Value();
        }
        
        return new AcceptedBids(selectedBids, totalValue, currentCompaniesCovered, currentRegionsCovered);
    }

    public AcceptedBids GetGreedyRankBasedInitialState() 
    {
        List<Bid> allBids = new ArrayList<Bid>(initialSetOfBids);
        Collections.sort(allBids, new RankBasedBidComparer());
        
        List<Bid> selectedBids = new ArrayList<Bid>();
        double totalValue = 0;
        List<Integer> currentCompaniesCovered = new ArrayList<Integer>();
        List<Integer> currentRegionsCovered = new ArrayList<Integer>();
        

        // Probabilistically select some initial bids
        for (int i = 0; i < allBids.size(); ++i)
        {
            Bid bid = allBids.get(i);
            
            if (currentCompaniesCovered.contains(bid.Company()))
            {
                continue;
            }
            
            boolean isAnyRegionCovered = false;
            
            for (int region : bid.Regions())
            {
                if (currentRegionsCovered.contains(region))
                {
                    isAnyRegionCovered = true;
                    break;
                }
            }
            
            if (isAnyRegionCovered)
            {
                continue;
            }
            
            if (ShouldSelectBid(bid.Rank()))
            {
                selectedBids.add(bid);
                currentCompaniesCovered.add(bid.Company());
                currentRegionsCovered.addAll(bid.Regions());
                totalValue += bid.Value();
            }
        }
        
        // try to fill in the bids just greedily now
        for (int i = 0; i < allBids.size(); ++i)
        {
            Bid bid = allBids.get(i);
            
            if (currentCompaniesCovered.contains(bid.Company()))
            {
                continue;
            }
            
            boolean isAnyRegionCovered = false;
            
            for (int region : bid.Regions())
            {
                if (currentRegionsCovered.contains(region))
                {
                    isAnyRegionCovered = true;
                    break;
                }
            }
            
            if (isAnyRegionCovered)
            {
                continue;
            }
            
            selectedBids.add(bid);
            currentCompaniesCovered.add(bid.Company());
            currentRegionsCovered.addAll(bid.Regions());
            totalValue += bid.Value();
        }
        
        return new AcceptedBids(selectedBids, totalValue, currentCompaniesCovered, currentRegionsCovered);
    }
    
    public AcceptedBids GetGreedyValueInitialState() 
    {
        List<Bid> allBids = new ArrayList<Bid>(initialSetOfBids);
        Collections.sort(allBids, new ValueBasedBidComparer());
        
        List<Bid> selectedBids = new ArrayList<Bid>();
        double totalValue = 0;
        List<Integer> currentCompaniesCovered = new ArrayList<Integer>();
        List<Integer> currentRegionsCovered = new ArrayList<Integer>();
        
        // try to fill in the bids just greedily
        for (int i = 0; i < allBids.size(); ++i)
        {
            Bid bid = allBids.get(i);
            
            if (currentCompaniesCovered.contains(bid.Company()))
            {
                continue;
            }
            
            boolean isAnyRegionCovered = false;
            
            for (int region : bid.Regions())
            {
                if (currentRegionsCovered.contains(region))
                {
                    isAnyRegionCovered = true;
                    break;
                }
            }
            
            if (isAnyRegionCovered)
            {
                continue;
            }
            
            selectedBids.add(bid);
            currentCompaniesCovered.add(bid.Company());
            currentRegionsCovered.addAll(bid.Regions());
            totalValue += bid.Value();
        }
        
        return new AcceptedBids(selectedBids, totalValue, currentCompaniesCovered, currentRegionsCovered);
    }
    
    public List<AcceptedBids> GetNeighboringStates(AcceptedBids currentState) 
    {
        List<AcceptedBids> neighborStates = new ArrayList<AcceptedBids>();
        
        for (int i = 0; i < currentState.Bids().size(); ++i)
        {
            neighborStates.addAll(GetStatesByRemovingBid(currentState.Bids().get(i), currentState));
        }
        
        return neighborStates;
    }
    
    public AcceptedBids GetRandomInitialState()
    {
        List<Integer> acceptedBidIds = new ArrayList<Integer>();
        Random random = new Random();
        Double totalValue = 0.0;

        ArrayList<Integer> availableBids = new ArrayList<Integer>();
        for (int i = 0; i < initialSetOfBids.size(); ++i)
        {
            availableBids.add(i);
        }

        while(availableBids.size() > 0)
        {
            int randomIndex = random.nextInt(availableBids.size());
            int bidId = availableBids.get(randomIndex);
            Bid chosenBid = initialSetOfBids.get(bidId);
            totalValue += chosenBid.Value();
            acceptedBidIds.add(bidId);

            List<Integer> bidsToRemove = new ArrayList<Integer>();

            Iterator<Integer> it = availableBids.iterator();
            while(it.hasNext())
            {
                int val = it.next();
                Bid currentBid = initialSetOfBids.get(val);

                if(chosenBid.Company() == currentBid.Company())
                {
                    bidsToRemove.add(val);
                    continue;
                }

                List<Integer> regions = new ArrayList<Integer>(currentBid.Regions());
                regions.retainAll(chosenBid.Regions());
                if(regions.size() > 0)
                {
                    bidsToRemove.add(val);
                }
            }

            availableBids.removeAll(bidsToRemove);
        }

        Collections.sort(acceptedBidIds);
        return PopulateAcceptedBids(acceptedBidIds);
    }

    private List<AcceptedBids> GetStatesByRemovingBid(
            Bid bidToRemove,
            AcceptedBids inputState) 
    {
        List<Bid> currentBids = new ArrayList<Bid>(inputState.Bids());
        currentBids.remove(bidToRemove);

        return GenerateNeighborsByAddingBids(currentBids);
    }

    private AcceptedBids PopulateAcceptedBids(List<Integer> acceptedBidIds) 
    {
        List<Bid> acceptedBids = new ArrayList<Bid>();
        double totalValue = 0;
        List<Integer> companiesCovered = new ArrayList<Integer>();
        List<Integer> regionsCovered = new ArrayList<Integer>();
        
        for (int i = 0; i < acceptedBidIds.size(); ++i)
        {
            Bid accceptedBid = initialSetOfBids.get(acceptedBidIds.get(i));
            totalValue += accceptedBid.Value();
            companiesCovered.add(accceptedBid.Company());
            regionsCovered.addAll(accceptedBid.Regions());
            acceptedBids.add(accceptedBid);
        }

        Collections.sort(companiesCovered);
        Collections.sort(regionsCovered);
        return new AcceptedBids(acceptedBids, totalValue, companiesCovered, regionsCovered);
    }

    private double PopulateDetailsFromBids(
            List<Bid> bids,
            List<Integer> outCompaniesCovered,
            List<Integer> outRegionsCovered) 
    {
        double totalValue = 0;
        
        for (Bid bid : bids)
        {
            totalValue += bid.Value();
            outCompaniesCovered.add(bid.Company());
            outRegionsCovered.addAll(bid.Regions());
        }

        return totalValue;
    }

    public void PrintAcceptedBids(AcceptedBids acceptedBids, ILogger logger)
    {
        StringBuffer sb = new StringBuffer();
        
        for (int i = 0; i < acceptedBids.Bids().size(); ++i)
        {
            sb.append(acceptedBids.Bids().get(i).BidId());
            sb.append(" ");
        }
        
        logger.LogInfo(sb.toString());
    }

    public void PrintAcceptedBidsWithDetails(AcceptedBids acceptedBids, ILogger logger)
    {
        logger.LogInfo("Total Value: %f", acceptedBids.TotalValue());
        logger.LogInfo("Companies covered: %s", acceptedBids.CompaniesCovered());
        logger.LogInfo("Regions covered: %s", acceptedBids.RegionsCovered());

        for (int i = 0; i < acceptedBids.Bids().size(); ++i)
        {
            logger.LogInfo("%s", acceptedBids.Bids().get(i));
        }
    }

    public AcceptedBids SelectHighestNeighbor(List<AcceptedBids> neighbouringStates) 
    {
        ArgumentValidator.IsNotNull("neighbouringStates", neighbouringStates);
        
        AcceptedBids maxAcceptedBidSet = neighbouringStates.get(0);
        
        for (int i = 1; i < neighbouringStates.size(); ++i)
        {
            if (maxAcceptedBidSet.TotalValue() < neighbouringStates.get(i).TotalValue())
            {
                maxAcceptedBidSet = neighbouringStates.get(i);
            }
        }
        
        return maxAcceptedBidSet;
    }

    private boolean ShouldSelectBid(double probability)
    {
        return this.randomGenerator.nextBoolean(probability);
    }
}
